package com.haidechizi.tree.search;

public class BinarySearchTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void addNode(Node node) {
        if (root == null) {
            this.root = node;
            return;
        }
        root.addNode(node);
    }

    public void midShow() {
        if (root == null) {
            return;
        }
        this.root.midShow();
    }

    public void frontShow() {
        if (this.root == null) {
            return;
        }
        this.root.frontShow();
    }

    public void afterShow() {
        if (this.root == null) {
            return;
        }
        this.root.afterShow();
    }

    public Node searchNode(int i) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchNode(i);
    }

    public Node searchParent(int value) {
        if (this.root == null) {
            return null;
        }
        return this.root.searchParent(value);
    }

    public void deleteNode(int i) {
        if (this.root == null) {
            return;
        }
        Node target = this.searchNode(i);
        if (target == null) {
            return;
        }
        Node parent = this.searchParent(i);


        // 连个节点都为空
        if (target.getLeft() == null && target.getRight() == null) {
            if (parent.getValue() > target.getValue()) {
                parent.setLeft(null);
            } else {
                parent.setRight(null);
            }
        } else if (target.getLeft() != null && target.getRight() != null) {

            // 删除后继节点
            int min = deleteMin(target.getRight());

            // 将删除节点的值替换Wie后继节点的值
            target.setValue(min);

            // 只要一个叶子节点
        } else {
            if (target.getLeft() != null) {
                // 左子节点
                if (parent.getValue() > target.getValue()) {
                    parent.setLeft(target.getLeft());
                    target.setLeft(null);
                } else {
                    parent.setRight(target.getLeft());
                    target.setLeft(null);
                }
            } else {
                // 要删除节点的右子节点不为空
                if (parent.getValue() > target.getValue()) {
                    parent.setLeft(target.getRight());
                    target.setRight(null);
                } else {
                    parent.setRight(target.getRight());
                    target.setRight(null);
                }
            }

        }
    }

    private int deleteMin(Node right) {
        Node target = right;
        while (target.getLeft() != null) {
            target = target.getLeft();
        }
        deleteNode(target.getValue());
        return target.getValue();
    }
}
